/*
* 1.左偏树/左式堆
    左偏树作为可并堆的一种数据结构，其重点在于将两个堆合并，
    在维护堆的性质之外，每个节点x另外维护一个信息dist[x]表示x到最近的叶子节点的距离
    且dist[l]>=dist[r]，从而保证合并复杂度O(logn) <- 根节点的距离<=logn


* 2.op
    (1) 插入一个数 O(logn)
    (2) 求最小值 O(1)
    (3) 删除最小值 O(logn)
    (4) 合并两棵树 O(logn)
        merge(a, b) 合并子树a,b，并返回合并后的根节点

*/ 

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define DEBUG
inline int read()
{
	int x=0;char c=getchar();
	while (c<'0'||c>'9') c=getchar();
	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+c-48,c=getchar();
	return x;
}
inline void write(int x)
{
    if(x<0) putchar('-'), x*=-1;
	if (x>=10) write(x/10);
	putchar(x%10+48);
}//快读快输
const int N=1e5+10;
int n, m, op, x, y;
int fa[N], val[N], l[N], r[N], dist[N];

bool cmp(int x, int y)
{
    return val[x]!=val[y]?val[x]<val[y]:x<y;
}

int find(int x)
{
    return x==fa[x]?x:fa[x]=find(fa[x]);
}

int merge(int x, int y)
{
    if(!x||!y) return x+y;
    if(cmp(y, x)) swap(x, y); //y<x(权值或顺序)
    r[x]=merge(r[x], y);
    if(dist[l[x]]<dist[r[x]]) swap(l[x], r[x]);
    dist[x]=dist[r[x]]+1;
    return x;
}

void pop(int x)
{
    val[x]=-1; //删除当前节点
    int y=merge(l[x],r[x]);
    fa[x]=y,fa[y]=y; //并查集换根
}

void solve()
{
    n=read(); m=read();
    
    for(int i=1; i<=n; i++)
    {
        val[i]=read();
        fa[i]=i;
        dist[i]=1;
    }

    for(int i=1; i<=m; i++)
    {
        op=read(); x=read();
        if(op==1) //合并x,y两个堆
        {
            y=read();
            if(val[x]<0||val[y]<0) continue; //当前节点不存在
            x=find(x), y=find(y);
            if(x!=y)
            {
                if(cmp(y, x)) swap(x, y); //y<x(权值或顺序)
                fa[y]=x; //y插入到x中
                merge(x, y);

            }
        }
        else if(op==2)
        {
            if(val[x]<0) {write(-1), puts("");; continue;} //节点不存在
            x=find(x);
            write(val[x]), puts("");pop(x);
        }
    } 
}

signed main()
{
    #ifdef DEBUG
        freopen("./in.txt","r",stdin);
        freopen("./out.txt","w",stdout);
    #endif

    
    int T=1; //T=read();
    while(T--)
    {
        solve();
    }
    return 0;
}